#include<stdio.h>
#include<stdlib.h>

/***
 * 算法题
 * */

// 1. 循环单链表 最少时间每个结点 向右移动k个单位
typedef struct Node
{
    int data;
    Node *next;
} LNode, *List;
// 1->2->3->4->5->，k=2
// 4->5->1->2->3->

// 方法按照带头结点写的
void MoveK(List &L, int k)
{
    LNode *ptr = L; // 工作结点
    // 求链表长度
    int length = 0;
    while (ptr->next != L)
    {
        ++length;
        ptr = ptr->next;
    }
    LNode *tail = ptr; // 尾部结点
    // 处理大于链表长度的情况
    k = k % length;
    ptr = L->next; // 新链表起始结点
    int step = 0;
    LNode *pre; // 新链表尾结点
    while (ptr != L)
    {
        pre = ptr;
        ptr = ptr->next;
        if (++step == length - k)
        {
            pre->next = L;        // 新尾结点指向头结点
            tail->next = L->next; // 原尾结点指向原第一个结点
            L->next = ptr;        // 头结点指向新链表
            break;
        }
    }
}

// 测试用
void Init(List &L)
{
    L = (LNode *)malloc(sizeof(LNode));
    L->data = 0;
    L->next = L;
}

void Append(List &L, int e)
{
    LNode *ptr = L; // 工作结点
    while (ptr->next != L)
        ptr = ptr->next;
    LNode *res = (LNode *)malloc(sizeof(LNode));
    res->data = e;
    res->next = L;
    ptr->next = res;
}

void Print(List L)
{
    LNode *ptr = L->next; // 工作结点
    printf("head->");
    while (ptr != L)
    {
        printf("%d->", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

int main()
{
    List L;
    Init(L);
    Append(L, 1);
    Append(L, 2);
    Append(L, 3);
    Append(L, 4);
    Append(L, 5);
    Print(L);
    MoveK(L, 2);
    Print(L);
    return 0;
}